package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.*;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/31 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 最长不含重复字符的子字符串 {

    public static int lengthOfLongestSubstring (String s) {
        Set<String> set = new HashSet<>();
        ArrayList<String> list = new ArrayList<>();

        // write code here
        int res=0,max=0;
        char[] chars = s.toCharArray();
        set.add(chars[0]+"");
        list.add(chars[0]+"");
        for (int i = 1; i < chars.length; i++) {


            if (!list.contains(chars[i]+"")){
                list.add(chars[i]+"");
                res++;
            }
            if (list.contains(chars[i]+"") ){
                list.clear();
                list.add(chars[i]+"");
                max= res ;
                res=0;
            }


        }
//        process(chars,0,"");
        return  max;
    }

    public int lengthOfLongestSubstring1 (String s) {
        Queue<Character> list = new LinkedList<>();
        int max=0;
        for (char c : s.toCharArray()) {
            while (list.contains(c)){
                list.poll();
            }
            list.add(c);
            max=Math.max(max,list.size());
        }
        return max;

    }
    public int lengthOfLongestSubstring2 (String s) {
        int left=0,right=0,curlen=0,max=0;
        Set<Character> set = new HashSet<>();
        while (right<s.length()){
            if (!set.contains(s.charAt(right))){
                set.add(s.charAt(right));
                right++;
                curlen++;
                max=Math.max(curlen,max);
            }else {

                // 此时set仍存在重复元素，则left移动
                while (set.contains(s.charAt(right))){
                    set.remove(s.charAt(left));
                    left++;
                    curlen--;
                }
                // 现在不重复了，
                set.add(s.charAt(right));
                curlen++;right++;

            }

        }
        return max;
    }

}
